package com.dataStructure.树.AVL树;

import java.util.Comparator;

//AVLTree是一种自平衡的二叉查找树，比二叉查找树多了，当平衡因子的绝对值大于1时，可以自平衡将左右子树高度差缩短到1以内
//继承自二叉查找树
public class AVLTree<E> extends BinarySearchTree<E> {
    //构造方法同样也要传入比较器
    public AVLTree() {
        this(null);
    }

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

    //是否平衡
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

    //AVLNode比普通Node多了height的概念，因为要自平衡的缘故
    private static class AVLNode<E> extends Node<E> {
        //才创建的是叶子节点，高度肯定为1
        int height = 1;

        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }

        //计算节点的平衡因子
        public int balanceFactor() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            return leftHeight - rightHeight;
        }

        // 更新自己的高度
        public void updateHeight() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            height = 1 + Math.max(leftHeight, rightHeight);
        }

        //找到自己左右子树比较高的那个子树
        public Node<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
            // return leftHeight > rightHeight ? ((AVLNode<E>) left):((AVLNode<E>) right);
            if (leftHeight > rightHeight) return left;
            if (rightHeight > leftHeight) return right;
            return isLeftChild() ? left : right;
        }

        @Override
        public String toString() {
            String parentString = null;
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h" + height + ")";
        }
    }

    //重写创建节点的方法 用以创造特有的AVLNode
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }

    //更新一下高度
    private void updateHight(Node<E> node) {
        ((AVLNode) node).updateHeight();
    }

    //bst的子类avltree来实现恢复平衡的逻辑
    @Override
    protected void afterAdd(Node<E> node) {
        //插入的节点开始，一直往上判断是否平衡
        while ((node = node.parent) != null) {
            //平衡
            if (isBalanced(node)) {
                //更新高度
                updateHight(node);
            } else {
                //恢复平衡
                rebalance(node);
                //当找到第一个不平衡的节点时，将他恢复平衡，整棵树即恢复平衡
                //整棵树恢复平衡
                break;
            }
        }
    }

    //恢复平衡
    //高度最低的不平衡节点
    private void rebalance(Node<E> grand) {
        //找到下面的两个节点，这两个节点必然是高度是grand节点较高的那一个子节点和parent节点较高的那一个子节点
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        //如果parent是 L
        if (parent.isLeftChild()) {
            if (node.isLeftChild()) { // LL
                rotateRight(grand);
            } else { // LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else {
            if (node.isLeftChild()) { // RL
                rotateLeft(parent);
                rotateRight(grand);
            } else { // RR
                rotateLeft(grand);
            }
        }
    }

    //左旋转
    private void rotateLeft(Node<E> grand) {
        //拿到parent节点。要进行左旋转，说明parent节点一定是grand节点的右子树
        Node<E> parent = grand.right;
        Node<E> child = parent.left;

        //旋转操作
        grand.right = child;
        parent.left = grand;

        //旋转之后进行一些更新父节点和更新高度的操作
        afterRotate(grand, parent, child);

    }


    //右旋转
    private void rotateRight(Node<E> grand) {
        //拿到parent节点。要进行右旋转，说明parent节点一定是grand节点的左子树
        Node<E> parent = grand.left;
        Node<E> child = parent.right;

        //旋转操作
        grand.left = child;
        parent.right = grand;

        //旋转之后进行一些更新父节点和更新高度的操作
        afterRotate(grand, parent, child);
    }

    //旋转之后进行一些更新父节点和更新高度的操作
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        //更新parent的父节点
        //将grand节点的父节点变成parent节点的父节点
        parent.parent = grand.parent;
        //并且判断grand节点在之前是他父节点的右节点还是左节点，并把这个父节点的左或右节点改成现在的parent
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
            //如果grand没有父节点,grand是根节点
        } else {
            root = parent;
        }
        //更新grand的右子树(Child节点)的父节点
        if (child != null) {
            child.parent = grand;
        }
        //更新grand的父节点
        grand.parent = parent;

        //更新高度
        updateHight(grand);
        updateHight(parent);
    }

    @Override
    protected void afterRmove(Node<E> node) {
        //删除的节点开始，一直往上判断是否平衡
        while ((node = node.parent) != null) {
            //平衡
            if (isBalanced(node)) {
                //更新高度
                updateHight(node);
            } else {
                //恢复平衡
                rebalance(node);
                //当找到第一个不平衡的节点时，将他恢复平衡，整棵树即恢复平衡
                //整棵树恢复平衡

                //如果是删除这个地方就不用break，就一直往上走，看有没有父节点是不平衡的
                //之前删除节点的时候，删除的这个节点的parent并没有指向为null，在这个node被gc之前，可以一直往上找父节点
                //break;
            }
        }
    }

    ////////////////////////////////-----------------------------------------------------------------------------------///////////////////////
    //统一旋转操作
    private void rotate(
            Node<E> r,
            Node<E> a, Node<E> b, Node<E> c
            , Node<E> d
            , Node<E> e, Node<E> f, Node<E> g) {

        //d会成为新的root，所以d的parent节点指向原来的root的parent节点
        d.parent = r.parent;
        //看看r是r.parent的左还是右节点
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }

        //处理a-b-c
        b.left = a;
        if (a != null) {
            a.parent = b;
        }
        b.right = c;
        if (c != null) {
            c.parent = b;
        }
        updateHight(b);

        //处理e-f-g
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        f.right = g;
        if (g != null) {
            g.parent = f;
        }
        updateHight(f);

        //处理b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHight(d);
    }

    //使用统一旋转操作来恢复平衡
    //把参数的顺序传递正确即可
    private void rebalance1(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) {
            if (node.isLeftChild()) { // LL
                rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
            } else { // LR
                rotate(grand,parent.left,parent,node.left,node,node.right,grand,grand.right);
            }
        } else {
            if (node.isLeftChild()) { // RL
                rotate(grand,grand.left,grand,node.left,node,node.right,parent,parent.right);
            } else { // RR
                rotate(grand,grand.left,grand,parent.left,parent,node.left,node,node.right);
            }
        }
    }
}